package it.storm.solution;

/**
 * 303. 区域和检索 - 数组不可变
 * https://leetcode-cn.com/problems/range-sum-query-immutable/
 */
public class Solutions_303 {
    public static void main(String[] args) {
        int[] nums = {-2, 0, 3, -5, 2, -1};

        NumArray obj = new NumArray(nums);
        int res1 = obj.sumRange(0, 2);  // output: 1
        System.out.println(res1);

        int res2 = obj.sumRange(2, 5);  // output: -1
        System.out.println(res2);

        int res3 = obj.sumRange(0, 5);  // output: -3
        System.out.println(res3);
    }
}

/**
 * 思路：前缀和
 * 修改 nums 数组：nums[5] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5]
 * 然后 {2, 5} 的区间和，等于 nums[5] - nums[1]
 */
class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        // 创建前缀和数组 A
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        this.nums = nums;
    }

    public int sumRange(int i, int j) {
        if (i == 0) {
            return nums[j];
        }
        return nums[j] - nums[i - 1];
    }
}
